#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "binarySearchTree.h"
typedef struct pair
{
    TreeNode *parent;
    TreeNode *child;
} Pair;

static Pair SeekItem(const Item *pitem, const Tree *ptree);
static TreeNode *MakeNode(const Item *pitem);
static void AddNode(TreeNode *pnode, TreeNode *proot);
static bool ToLeft(const Item *pitemOrigin, const Item *pitemRoot);
static bool ToRight(const Item *pitemOrigin, const Item *pitemRoot);
static void InOrder(const TreeNode *rootNode, void (*pFunction)(Item item));
static void DeleteNode(TreeNode **pParentNode);
static void DeleteAllNodes(TreeNode *pRootNode);

/**
 * @brief 初始化树结构
 *
 * @param ptree
 */
void InitializeTree(Tree *ptree)
{
    ptree->size = 0;
    ptree->root = NULL;
}

/**
 * @brief 判断树是否为空
 *
 * @param ptree 传入的树
 * @return true 成功
 * @return false 失败
 */
bool TreeIsEmpty(const Tree *ptree)
{
    // 为什么书中没有使用下面这种方法>?
    // return ptree->root == NULL;
    if (ptree->root == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * @brief 判断树是否为满
 *
 * @param ptree 传入的树
 * @return true 成功
 * @return false 失败
 */
bool TreeIsFull(const Tree *ptree)
{
    if (ptree->size == MAXITEMS)
    {
        return true;
    }
    else
        return false;
}

/**
 * @brief 返回树中的项数
 *
 * @param ptree 传入的树
 * @return unsigned int
 */
unsigned int TreeItemCount(const Tree *ptree)
{
    return ptree->size;
}

/**
 * @brief 向树中添加项
 *
 * @param pitem 待添加的项
 * @param ptree 传入root树
 * @return true 成功
 * @return false 失败
 */
bool AddItemToTree(const Item *pitem, Tree *ptree)
{
    // 检查Tree是否满
    if (TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree Is FULL!\n");
        return false;
    }

    // 检查Tree中是否存在重复的项
    if (SeekItem(pitem, ptree).child != NULL)
    {
        fprintf(stderr, "Attemped to add deplicate item\n");
        return false;
    }
    // 检查完成,将Item包装成Node
    TreeNode *newnode;
    newnode = MakeNode(pitem); // 负责分配空间
    if (newnode == NULL)
    {
        fprintf(stderr, "Can't create Item to Node!\n");
        return false;
    }

    // 成功创建了一个节点
    ptree->size++;
    // 首个节点 root
    if (ptree->root == NULL)
    {
        ptree->root = newnode;
        return true;
    }
    // 不是首个节点P
    else
    {
        AddNode(newnode, ptree->root);
    }
    return true;
}

/**
 * @brief 从树中查找对应的项
 *
 * @param pitem 需要查找的Item指针
 * @param ptree 传入的树
 * @return true 查找到项
 * @return false 没有此项
 */
bool FindItemFromTree(const Item *pitem, Tree *ptree)
{
    return (SeekItem(pitem, ptree).child == NULL) ? true : false;
}

/**
 * @brief 从树中删除项
 *
 * @param pitem 待删除项
 * @param ptree
 * @return true 成功
 * @return false 失败
 */
bool DeleteItemFromTree(const Item *pitem, Tree *ptree)
{
    //必须标识待删除元素的父节点
    //为了修改指针,必须传递一个指向指针的指针给 处理函数
    Pair look;
    look = SeekItem(pitem, ptree);
    if (look.child == NULL)
    {
        return false;
    }
    if (look.parent == NULL) // 查找到的为根root
    {
        DeleteNode(&ptree->root);
    }
    else if (look.parent->leftnode == look.child)
    {
        DeleteNode(&look.parent->leftnode);
    }
    else
    {
        DeleteNode(&look.parent->rightnode);
    }
    ptree->size--;

    return true;
}

/**
 * @brief 为每一个树中的元素执行一次传入的函数
 *
 * @param ptree 传入的树
 * @param pFunction 待执行的每一个函数
 */
void TreeTraverse(const Tree *ptree, void (*pFunction)(Item pitem))
{
    if (ptree != NULL)
    {
        InOrder(ptree->root, pFunction);
    }
}

/**
 * @brief 清除树中的所有元素
 *
 * @param tree 传入待释放的树
 */
void DropTree(Tree *ptree)
{
    if (ptree != NULL)
    {
        DeleteAllNodes(ptree->root);
    }
    ptree->root = NULL;
    ptree->size = 0;
}

/**
 * @brief 检查Tree中是否存在重复的项(查找项函数)
 *
 * @return Pair (child为定位完成的目标pNode,parent为目标pNode的上一级pNode)
 */
static Pair SeekItem(const Item *pitem, const Tree *ptree)
{
    // 这里的pair是一个双指针结构,Pair中的child指向子节点,parent指向父节点
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;
    //到这里是初始化到根节点,parent为NULL,ptree为根节点

    if (look.child == NULL)
    {
        return look; // 提前退出,这时的返回值为: Pair(parent为NULL,child为NULL)
    }

    //这里没有像AddNode()函数一样使用递归调用的方式进行查找,而是使用while循环的方式
    while (look.child != NULL) // root下有节点
    {
        if (ToLeft(pitem, &(look.child->item))) // 向左定位
        {
            look.parent = look.child;
            look.child = look.child->leftnode;
        }
        else if (ToRight(pitem, &(look.child->item))) // 向右定位
        {
            look.parent = look.child;
            look.child = look.child->rightnode;
        }
        else
        {
            break; // while如果在这里结束,意味着相等
        }
    }
    // 定位完成,这时的返回值为 Pair(child为定位完成的目标pNode,parent为目标pNode的上一级pNode)
    return look;
}

/**
 * @brief 内部函数,用于分配空间,将Item包装成Node,并返回
 *
 * @param pitem 传入的Item
 * @return TreeNode* 返回包装好的Node
 */
static TreeNode *MakeNode(const Item *pitem)
{
    TreeNode *new_node;
    new_node = (TreeNode *)malloc(sizeof(TreeNode));
    if (new_node != NULL)
    {
        new_node->leftnode = NULL;
        new_node->rightnode = NULL;
        new_node->item = *pitem;
    }

    return new_node;
}

/**
 * @brief 内部核心函数,用于添加非根Node到Tree中
 *
 * @param pnode 包装好的Node
 * @param proot
 * @return true 成功
 * @return false 失败
 */
static void AddNode(TreeNode *pnode, TreeNode *proot)
{
    // 如果进入到了这个函数,意味着已经排除了在根节点进行填充(必须在左或右)
    if (ToLeft(&pnode->item, &proot->item))
    {
        if (proot->leftnode == NULL)
        {
            proot->leftnode = pnode; // 找到了对应的位置
        }
        else
        {
            //这里是一层递归调用,实现根节点向右内层移动,处理子树(没有找到对应的位置)
            AddNode(pnode, proot->leftnode);
        }
    }
    else if (ToRight(&pnode->item, &proot->item))
    {
        if (proot->rightnode == NULL)
        {
            proot->rightnode = pnode; // 找到了对应的位置
        }
        else
        {
            //这里是一层递归调用,实现根节点向左内层移动,处理子树(没有找到对应的位置)
            AddNode(pnode, proot->rightnode);
        }
    }
    else
    {
        // 打印这样的语句有可能有重复的项
        fprintf(stderr, "ERROR! Can't find right location in AddNode()!");
        exit(-1);
    }
}

/**
 * @brief 内部核心函数,用于判定元素处于每一个子树的左面
 *
 * @param itemOrigin 传入的待加入的item地址
 * @param itemRoot 相对的子树的item地址
 * @return true 在左边
 * @return false 失败
 */
static bool ToLeft(const Item *pitemOrigin, const Item *pitemRoot)
{
    //这里是一个自定义的判断排序的函数,进入这个函数的每一个排序需要通过这个向左(右)的函数完成
    int compared;
    if ((compared = strcmp(pitemOrigin->petName, pitemRoot->petName)) < 0)
    {
        return true;
    }
    else if (compared == 0 && (strcmp(pitemOrigin->petkind, pitemRoot->petkind)) < 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * @brief 内部核心函数,用于判定元素处于每一个子树的右面
 *
 * @param itemOrigin 传入的待加入的item地址
 * @param itemRoot 相对的子树的item地址
 * @return true 在右边
 * @return false 失败
 */
static bool ToRight(const Item *pitemOrigin, const Item *pitemRoot)
{
    int compared;
    if ((compared = strcmp(pitemOrigin->petName, pitemRoot->petName)) > 0)
    {
        return true;
    }
    else if (compared == 0 && (strcmp(pitemOrigin->petkind, pitemRoot->petkind)) > 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * @brief 内部函数, 传入一个函数和一个root,本函数进行数中的遍历
 *
 * @param rootNode
 * @param pFunction
 */
static void InOrder(const TreeNode *rootNode, void (*pFunction)(Item item))
{
    if (rootNode != NULL)
    {
        InOrder(rootNode->leftnode, pFunction);
        (*pFunction)(rootNode->item);
        InOrder(rootNode->rightnode, pFunction);
    }
}

/**
 * @brief 内部函数,递归调用删除所有的TreeNode
 *
 * @param pRootNode 传入root树指针
 */
static void DeleteAllNodes(TreeNode *pRootNode)
{
    TreeNode *treeNode;
    if (pRootNode != NULL)
    {
        treeNode = pRootNode->rightnode;
        DeleteAllNodes(pRootNode->leftnode);
        free(pRootNode);
        DeleteAllNodes(treeNode);
    }
}

/**
 * @brief 删除一个节点,并实现后续节点的拼接
 *
 * @param pParentNode 指向目标节点的父级节点指针成员的地址指针
 */
static void DeleteNode(TreeNode **pParentNode)
{
    TreeNode *temp;

    //父节点中左或者右右一项为NULL

    // 没有左节点的节点(和没有任何节点的节点)
    if ((*pParentNode)->leftnode == NULL)
    {
        temp = *pParentNode;                      //获得父级节点原来的TreeNode指针
        *pParentNode = (*pParentNode)->rightnode; //将父级节点更新成右面的TreeNode,实现连接
        free(temp);                               //将父级原来的位置free
    }
    // 没有右节点的节点
    else if ((*pParentNode)->rightnode == NULL)
    {
        temp = *pParentNode;
        *pParentNode = (*pParentNode)->leftnode; //连接树
        free(temp);
    }
    else // 有左右两项的(父级)节点
    {
        // 查找重新连接的右子树的位置,(从父级的左项开始,逐级向右下查找,直到右项为NULL,即为所得待插入地址)
        for (temp = (*pParentNode)->leftnode; temp->rightnode != NULL; temp = temp->rightnode)
        {
            continue;
        }
        //这时的temp为找到的插入地址
        temp->rightnode = (*pParentNode)->rightnode; //本级待删除,本级的右节点连接到待插入地址
        temp = *pParentNode;                         //准备释放本级
        *pParentNode = (*pParentNode)->leftnode;
        free(temp);
    }
}